include ExtLib.List;

type mut_list 'a =  {
  hd: 'a;
  tl: mutable list 'a
};

external inj : mut_list 'a -> list 'a = "%identity";
value dummy_node () = { hd = Obj.magic (); tl = [] };

value remove_exn l x =
  let rec loop dst = fun
    [ [] -> raise Not_found
    | [ h :: t ] ->
      if x = h
      then dst.tl := t
      else
        let r = { hd = h; tl = [] } in
        (
          dst.tl := inj r;
          loop r t
        )
    ]
  in
  let dummy = dummy_node () in
  (
    loop dummy l;
    dummy.tl
  );

value remove_if_exn f l =
  let rec loop dst = fun
    [ [] -> raise Not_found
    | [ h :: t ] ->
      if f h
      then dst.tl := t
      else
        let r = { hd = h; tl = [] } in
        (
          dst.tl := inj r;
          loop r t
        )
    ]
  in
  let dummy = dummy_node () in
  (
    loop dummy l;
    dummy.tl
  );


value pop_assoc x lst =
  let rec loop dst = fun
    [ [] -> raise Not_found
    | [ ((a,v) as pair) :: t ] ->
      if a = x
      then
      (
        dst.tl := t;
        v
      )
      else
        let r = { hd = pair; tl = [] } in
        (
          dst.tl := inj r;
          loop r t
        )
    ]
  in
  let dummy = dummy_node () in
  (
    let v = loop dummy lst in
    (v,dummy.tl);
  );


value pop_if f lst =
  let rec loop dst = fun
    [ [] -> raise Not_found
    | [ v :: t ] ->
      if f v
      then
      (
        dst.tl := t;
        v
      )
      else
        let r = { hd = v; tl = [] } in
        (
          dst.tl := inj r;
          loop r t
        )
    ]
  in
  let dummy = dummy_node () in
  (
    let v = loop dummy lst in
    (v,dummy.tl);
  );


value rec replace_assoc k v lst =
  let r = { hd = (k,v); tl = [] } in
  let rec loop dst = fun
    [ [] -> dst.tl := inj r
    | [ (k',_) :: tl ] when k' = k ->
      (
        r.tl := tl;
        dst.tl := inj r;
      )
    | [ h :: tl ] ->
      let r = { hd = h; tl = [] } in
      (
        dst.tl := inj r;
        loop r tl
      )
    ]
  in
  let dummy = dummy_node () in
  (
    loop dummy lst;
    dummy.tl;
  );
(*возвращает элементы первого списка, которых нет во вотором*)
value diff l1 l2 =
  fold_left (fun r e ->
    if mem e l2
    then r
    else [e :: r]
  ) [] l1;


value full_uniq_diff l1 l2 =
  let l2 = ref l2 in
  let res =
    fold_left (fun r e ->
      try
        l2.val := remove_exn !l2 e;
        r
      with [ Not_found -> [ e :: r] ]
    ) [] l1
  in
  (!l2,res);

value rec find_map f = fun
  [ [] -> raise Not_found
  | [ h :: tl ] ->
      match f h with
      [ None -> find_map f tl
      | Some r -> r
      ]
  ];


value split3 lst =
	let rec loop adst bdst cdst = fun
		[ [] -> ()
    | [ (a, b, c) :: t ] ->
			let x = { hd = a; tl = [] }
			and y = { hd = b; tl = [] }
      and z = { hd = c; tl = [] } in
      (
        adst.tl := inj x;
        bdst.tl := inj y;
        cdst.tl := inj z;
        loop x y z t
      )
    ]
	in
	let adummy = dummy_node ()
	and bdummy = dummy_node ()
  and cdummy = dummy_node ()
	in
  (
    loop adummy bdummy cdummy lst;
    (adummy.tl, bdummy.tl, cdummy.tl)
  );

(* возвращает номер элемента в списке удовлетворяющего условию *)
value eth (f:('a -> bool)) (lst:list 'a) =  
  let rec loop i = fun
    [ [] -> raise Not_found
    | [hd::tl] when (f hd) -> i
    | [_::tl] -> loop (i+1) tl
    ]
  in loop 0 lst;
